﻿#include<iostream>
using namespace std;
//#include<vector>
//#include<algorithm>
typedef long long ll;
#include<bits/stdc++.h>

//day 10.10[蓝桥杯 2022 国 A] 环境治理（C++，Floyd，二分法）
//ll ans = -1;
//
//ll n, Q;
//vector<vector<ll>>D;
//vector<vector<ll>>dist;
//vector<vector<ll>>Min;
//
//bool floyd(int day)
//{
//
//    for (int i = 0; i < n; ++i)
//    {
//        for (int j = 0; j < n; ++j)
//        {
//            dist[i][j] = D[i][j];
//        }
//    }
//    //除尘
//    for (int i = 0; i < n; ++i)
//    {
//        for (int j = 0; j < n; ++j)
//        {
//            dist[i][j] = dist[j][i] = max(dist[i][j] - day / n - (day % n >= i + 1 ? 1 : 0), Min[i][j]);
//        }
//    }
//
//    for (int i = 0; i < n; i++)
//    {//以i为中间点，Floyd
//        for (int j = 0; j < n; j++)
//        {
//            for (int z = 0; z < n; z++)
//            {
//                dist[j][z] = min(dist[j][z], dist[j][i] + dist[i][z]);
//            }
//        }
//    }
//
//    //计算是否满足小于等于Q
//    int sum = 0;
//    for (int i = 0; i < n; ++i)
//    {
//        for (int j = 0; j < n; ++j)
//        {
//            sum += dist[i][j];
//        }
//    }
//    if (sum >= 0 && sum <= Q)
//    {
//        ans = day;
//        return true;
//    }
//    else 
//    {
//        return false;
//    }
//}
//
//int main()
//{
//    cin >> n >> Q;
//    D = vector<vector<ll>>(n, vector<ll>(n));
//    dist = vector<vector<ll>>(n, vector<ll>(n));
//    Min = vector<vector<ll>>(n, vector<ll>(n));
//    for (int i = 0; i < n; ++i)
//    {
//        for (int j = 0; j < n; ++j)
//        {
//            cin >> D[i][j];
//        }
//    }//初始化D矩阵
//
//    for (int i = 0; i < n; ++i)
//    {
//        for (int j = 0; j < n; ++j)
//        {
//            cin >> Min[i][j];
//        }
//    }
//
//
//    int left = -1, right = 1e9;//题目没指定天数上限，可能有多轮治理
//    while (left + 1 != right)//二分
//    {
//        int mid = (left + right) / 2;
//
//        if (floyd(mid))//如果能够达成条件，说明该mid可能为目标
//        {
//            right = mid;
//        }
//        else
//        {
//            left = mid;//说明该mid不为目标天数
//        }
//    }
//    cout << ans;
//    return 0;
//}


// Excel地址 2017省赛
//int main()
//{
//    ll n;
//    cin >> n;
//    string s;
//    while (n > 0)
//    {
//        n--;
//        s = char(n % 26 + 'A') + s;
//        n /= 26;
//    }
//    cout << s << endl;
//    return 0;
//}
//
//
////分布式排列  2024 省赛  模拟
//
//int main()
//{
//    int N;
//    cin >> N;
//    vector<vector<int>>arr(N);
//    vector<int>count(N, 0);
//    int ans = 0;
//    while (1)
//    {
//        string s;
//        cin >> s;
//        if (cin.fail() || s.empty())
//        {
//            break;
//        }
//        int num;
//        if (s == "add")
//        {
//            cin >> num;
//            arr[0].push_back(num);
//        }
//        else if (s == "sync")
//        {
//            cin >> num;
//            if (count[num] < arr[0].size())
//            {
//                arr[num].push_back(arr[0][count[num]]);
//                count[num]++;
//            }
//        }
//        else
//        {
//            int Min = 1e5;
//            for (int i = 0; i < N; ++i)
//            {
//                if (arr[i].size() < Min)
//                {
//                    Min = arr[i].size();
//                }
//            }
//
//            for (int i = ans; i < Min; ++i)
//            {
//                int n = arr[0][i];
//                for (int j = 1; j < N; ++j)
//                {
//                    if (arr[j][i] != n)
//                    {
//                        break;
//                    }
//                    if (j + 1 == N)
//                    {
//                        ans++;
//                    }
//                }
//            }
//            cout << ans << endl;
//        }
//    }
//    return 0;
//}

// 10.14 食堂  省赛  贪心
//一共12种情况，6人桌8种，四人桌4种
//先考虑6人桌


//#include <iostream>
//using namespace std;
//int main()
//{
//    int q;
//    cin >> q;
//    while (q--)
//    {
//        int a2, a3, a4, b4, b6;
//        int sum = 0;
//        cin >> a2 >> a3 >> a4 >> b4 >> b6;
//        if (b6 > 0)//3+3
//        {
//            int n = min(b6, a3 / 2);
//            sum += 6 * n;
//            b6 -= n, a3 -= 2 * n;
//        }
//
//        if (b6 > 0)//4+2
//        {
//            int n = min(b6, min(a4, a2));
//            sum += n * 6;
//            b6 -= n, a4 -= n, a2 -= n;
//        }
//
//        if (b6 > 0)//2+2+2
//        {
//            int n = min(b6, a2 / 3);
//            sum += n * 6;
//            b6 -= n, a2 -= 3 * n;
//        }
//
//        if (b6 > 0)//3+2
//        {
//            int n = min(b6, min(a3, a2));
//            sum += 5 * n;
//            b6 -= n, a3 -= n, a2 -= n;
//        }
//
//        if (b6 > 0)//4
//        {
//            int n = min(b6, a4);
//            sum += 4 * n;
//            b6 -= n, a4 -= n;
//        }
//        if (b6 > 0)//2+2 
//        {
//            int n = min(b6, a4 / 2);
//            sum += 4 * n;
//            b6 -= n, a4 -= n * 2;
//        }
//
//        if (b6 > 0)//3
//        {
//            int n = min(b6, a3);
//            sum += 3 * n;
//            b6 -= n, a3 -= n;
//        }
//        if (b6 > 0)//2
//        {
//            int n = min(b6, a2);
//            sum += 2 * n;
//            b6 -= n, a2 -= n;
//        }
//
//        if (b4 > 0)
//        {
//            int n = min(b4, a4);
//            sum += 4 * n;
//            b4 -= n, a4 -= n;
//        }
//
//        if (b4 > 0)//2+2
//        {
//            int n = min(b4, a2 / 2);
//            sum += 4 * n;
//            b4 -= n, a2 -= 2 * n;
//        }
//
//        if (b4 > 0)//3
//        {
//            int n = min(b4, a3);
//            sum += 3 * n;
//            b4 -= n, a3 -= n;
//        }
//
//        if (b4 > 0)//2
//        {
//            int n = min(b4, a2);
//            sum += 2 * n;
//            b4 -= n, a2 -= n;
//        }
//        cout << sum << endl;
//    }
//    return 0;
//}


//本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
//2021 是一个特殊的年份，它的千位和十位相同，个位比百位多一。请问从 1000(含)到9999(含)有多少个这样的年份 ?

//81


//小蓝有一个超大的仓库，可以摆放很多货物，
//现在，小蓝有, 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高.
//小蓝希望所有的货物最终摆成一个大的长方体。即在长.宽、高的方向上分别堆L、W、H 的货物, 满足 n ≡  xWxH.
//给定 n，请问有多少种堆放货物的方案满足要求,
//例如，当几 = 4时，有以下6种方案:1x1x4、1x2x2、1x4x1、2x1x2、2x2x1、4x1x1
//请问，当n = 2021041820210418(注意有 16 位数字)时，总共有多少种方案 ?

//int main()
//{
//    ll n = 2021041820210418;
//    ll L, W, H;
//    ll sum = 0;
//    for (L = 1; L * L * L <= n; ++L)
//    {
//        if (n % L == 0)
//        {
//            for (W = L; W * W * L <= n; ++W)
//            {
//                if (n / L % W == 0)
//                {
//                    if (L * W < n)
//                    {
//                        H = n / L / W;
//                        if (L == W && W == H)//不管顺序，先计算总共的组合数，随后根据这些组合数的状态获得答案
//                        {
//                            sum += 1;
//                        }
//                        else if (L == W || W == H || H == L)
//                        {
//                            sum += 3;
//                        }
//                        else
//                        {
//                            sum += 6;
//                        }
//                    } 
//                }
//            }
//        }
//    }
//
//    cout << sum << endl;
//    return 0;
//}



//省赛, 动态规划, 状压DP

//蓝桥学院由21​​​ 栋教学楼组成，教学楼编号1到21.对于两栋教学楼​a,b​ 互质时，a,b 之间有一条走廊直接相连，
//两个方向皆可通行，否则没有直接连接的走廊。
//
//小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路）
//，请问他有多少种不同的访问方案？
//
//两个访问方案不同是指存在某个i，小蓝在两个访问方法中访问完教学楼i 后访问了不同的教学楼。
//状态压缩：使用一个二进制位的状态表示当前访问了哪些节点。
// 例如，状态 state = 0b01101 表示节点1、3、4已被访问。
//提示：建议使用计算机编程解决问题。

//int gcd(int a, int b)//欧几里得算法求最大公约数
//{
//	if (a < b)
//	{
//		return gcd(b, a);
//	}
//	if (b == 0)
//	{
//		return a;
//	}
//
//	return gcd(b, a % b);
//}
//
//const int N = 21;
//int main()
//{
//	vector<vector<ll>>AM(N + 1, vector<ll>(N + 1));//邻接矩阵
//	for (int i = 1; i <= N; ++i)
//	{
//		for (int j = 1; j <= N; ++j)
//		{
//			if (gcd(i, j) == 1)
//			{
//				AM[i][j] = AM[j][i] = 1;//表示i与j楼之间有路
//			}
//		}
//	}
//
//	//一共有2^21种状态，但全为0的话没意义，总状态数量就是2^21-1
//	vector<vector<ll>>dp(1 << N, vector<ll>(N + 1 , 0));
//	// 状态压缩DP，dp[state][i]表示当前访问过的状态是state，且停留在i的方案数
//	dp[1][1] = 1;//// 初始状态：从教学楼1开始
//
//	for (int state = 1; state < (1 << 21); state += 2)
//	{
//		for (int i = 1; i <= 21; ++i)
//		{
//			if (!(state & (1 << (i - 1))))//状态的第0位是第一座教学楼，这里在1左移之前要先转化一下i
//				//&操作符有0为0，计算第i栋楼是否到达过，没有到达过就continue
//				//状态中不包含i教学楼，跳过
//			{
//				continue;
//			}
//
//
//			// 尝试从i移动到其他未访问的教学楼j
//			//初始出发点是1，所以j只能从2开始
//			for (int j = 2; j <= 21; j++)
//			{
//				if (state & (1 << (j - 1)))// 教学楼j已经访问过
//				{
//					continue;
//				} 
//				if (AM[i][j]) // i和j互质有道路，可以相连
//				{
//					dp[state | (1 << (j - 1))][j] += dp[state][i];
//					//dp[state | (1<<(j-1))][j]代表从之前的state状态，到达j的状态（前提是有路）,此时
//				}
//			}
//		}
//	}
//
//	ll ans = 0;
//	int finalState = (1 << 21) - 1;
//	for (int i = 2; i <= N; i++)//这里的i表示是回到1前的教学楼
//	{
//		if (AM[i][1]) // i和1互质，可以回到1
//		{
//			ans += dp[finalState][i];
//		}
//	}
//
//	cout << ans << endl;//881012367360
//
//	return 0;
//}



// 10.17   规律, 思维, 省赛

//最少砝码
// 
//你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于
//N 的正整数重量。
//
//那么这套砝码最少需要包含多少个砝码？
//注意砝码可以放在天平两边。

//注意规律三进制

//1 3可测1-4所有
// 1 3 9可以测1-13所有的数字
// 1 3 8 27 可以测40以内所有的数

//int main()
//{
//	ll n;
//	cin >> n;
//	int ans = 0;
//	int num = 0;
//	int i = 0;
//	while (n > num)
//	{
//		num += pow(3, i);
//		i++;
//		ans++;
//	}
//	
//	cout << ans << endl;
//	return 0;
//}


// 0路径 省赛, 动态规划, LCM, 最短路问题

//他定义了一个特别的图，希望找到图 中的最短路径。
//
//小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
//
//对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
//
//例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
//
//请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
////Dijkstra版本
// 
// 
//const int N = 2021;
//
//int gcd(int a, int b)
//{
//    if (b == 0)
//    {
//        return a;
//    }
//
//    return gcd(b, a % b);
//}
//
//int AM[2022][2022];
//
//int main()
//{
//
//    for (int i = 1; i <= N; ++i)
//    {
//        for (int j = 1; j <= N; ++j)
//        {
//            AM[i][j] = -1;  // 初始化为 -1，表示无连接
//        }
//    }
//
//    for (int i = 1; i <= N; ++i)
//    {
//        for (int j = 1; j <= N; ++j)
//        {
//            if (abs(i - j) <= 21)
//            {
//                int GCD = gcd(i, j);
//                int LCM = (i * j) / GCD;
//                AM[i][j] = AM[j][i] = LCM;
//            }
//        }
//    }//创建邻接矩阵
//
//    vector<int>dp(N + 1, INT_MAX);//dp[i]表示从1到i的最短路径
//    priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;//从1到i的最短路径，i节点
//
//    dp[1] = 0;
//    pq.push({ 0,1 });//节点1到节点1的距离为0
//
//    while (pq.size())//优先处理离1距离较短的节点
//    {
//        auto it = pq.top();
//        pq.pop();
//
//        if (it.first > dp[it.second])//如果之前处理过it.second的距离并更新到dp[it.second]中，就有可能会出现这个情况
//        {
//            continue;
//        }
//
//        for (int i = max(1, it.second - 21); i <= min(N, it.second + 21); ++i)
//        {
//            if (AM[it.second][i] != -1)//说明两个节点之间有路径
//            {
//                int len = AM[it.second][i];
//                if (len + dp[it.second] < dp[i])
//                {
//                    dp[i] = len + dp[it.second];
//                    pq.push({ dp[i],i });//再把这次求得最小加入队列
//                }
//            }
//        }
//    }
//
//    cout << dp[2021] << endl;
//    return 0;
//}

//动态规划版

//const int N = 2021;
//
//// 计算最大公约数
//int gcd(int a, int b)
//{
//    if (b == 0)
//    {
//        return a;
//    }
//    return gcd(b, a % b);
//}
//
//int main()
//{
//    vector<int> dp(N + 1, INT_MAX);  // dp[i] 表示从节点 1 到节点 i 的最短路径
//    dp[1] = 0;  // 起点到自身的距离为 0
//
//    // 动态规划计算最短路径
//    for (int i = 1; i <= N; ++i)
//    {
//        // 更新与节点 i 相连的节点的最短路径
//        for (int j = i + 1; j <= min(N, i + 21); ++j)
//        {
//            int GCD = gcd(i, j);
//            int LCM = (i / GCD) * j;  // 计算最小公倍数
//            dp[j] = min(dp[j], dp[i] + LCM);
//            // 更新从 1 到 j 的最短路径
//
//        }
//    }
//
//    // 输出从 1 到 2021 的最短路径
//    cout << dp[2021] << endl;
//
//    return 0;
//}


//省赛，单位换算

//小蓝要和朋友合作开发一个时间显示的网站。
//
//在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从
//1970 年1 日00 : 00 : 00 到当前时刻经过的毫秒数。
//现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
//给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
//输入描述
//输入一行包含一个整数，表示时间。
//输出描述
//输出时分秒表示的当前时间，格式形如 HH : MM:SS，其中 HH 表示时，
// 值为	0​​​​ 到23​​​​，MM 表示分，值为0​​​​ 到59​​​，SS 表示秒，值为0​​ 到59​。时、分、秒 不足两位时补前导0。

//#include<bits/stdc++.h>
//using namespace std;
//
//int main()
//{
//	ll n;
//	cin >> n;
//	n /= 1000;
//	ll t = 60 * 60 * 24;
//	ll x = n % t;
//	int hour, minute, second;
//	hour = x / 3600;
//	x %= 3600;
//	minute = x / 60;
//	second = x % 60;
//	printf("%02d:%02d:%02d\n", hour, minute, second);
//	return 0;
//}


//省赛, 树形DP, 动态规划

